<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8" />
    </head>
<xmp theme="united" style="display:none;">
# 排序算法
***
```java
/**
 * @description: 冒泡排序
 * 从第一个数开始，两两比较，前一个比较大就交换，这样一轮下来，最大的就被换到最后
 * 然后再从头开始，一共n轮
 * @author: lilin
 * @create: 2019-08-15 16:11
 **/
public class BubbleSort {

    public static void sort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    Util.swap(arr, j, j + 1);
                }
            }
        }
    }
}
```

```java
/**
 * @description: 选择排序
 * 从第一个数开始，每次选出它后面的数里面，比它小的，最小的一个，跟它交换
 * 这样最小的数就到了最前面
 * 接下来再从第二个数开始重复此操作
 * @author: lilin
 * @create: 2019-08-15 16:52
 **/
public class SelectSort {

    public static void sort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int min = arr[i];
            int index = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    index = j;
                }
            }
            Util.swap(arr, i, index);
        }
    }
}
```

```java
/**
 * @description: 插入排序
 * 第一个数默认位置是正确的，作为基准数，从第二个数开始
 * 如果比基准数大，那说明位置暂时正确
 * 如果比基准数小，那么指针不断前移，直到找到一个合适的位置，插入进去
 * @author: lilin
 * @create: 2019-08-15 17:08
 **/
public class InsertSort {

    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int target = arr[i];
            int j = i - 1;
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > target) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = target;
        }
    }
}
```

```java
/**
 * @description: 快排
 * 选定一个基准数，或者叫哨兵
 * 一头一尾两个指针i和j
 * j向前移动，找到第一个比基准数小的；i向后移动，找到第一个比基准数大的
 * 交换，然后继续移动直到两个指针相遇，然后交换基准数和相遇位置的这个数
 * 相遇位置的这个数其实就是i指针最后一次指向的位置，但是因为上一步交换了i和j
 * 因此这个数，比基准数小
 * 一趟下来，把比它小的移到它左边，比它大的移到它右边
 * 然后再以这个数为分界，左右两边递归地进行快排
 * @author: lilin
 * @create: 2019-08-16 14:36
 **/
public class QuickSort {
    // 一次划分过程，选定最左边的数为基准数
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (arr[j] >= pivot && i < j) {
                j--;
            }
            while (arr[i] <= pivot && i < j) {
                i++;
            }
            Util.swap(arr, i, j);
        }
        Util.swap(arr, left, i);
        return i;
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }

    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
}
```

```java
/**
 * @description: 归并排序
 * @author: lilin
 * @create: 2019-08-20 10:03
 **/
public class MergeSort {
    public static void sort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        // merge两个数组 [left, mid], [mid + 1, right]
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                i++;
            } else {
                temp[k] = arr[j];
                j++;
            }
            k++;
        }
        while (i <= mid) {
            temp[k] = arr[i];
            k++;
            i++;
        }
        while (j <= right) {
            temp[k] = arr[j];
            k++;
            j++;
        }
        for (int l = left; l <= right; l++) {
            arr[l] = temp[l - left];
        }
    }
}
```

```java
/**
 * @description: 计数排序
 * 有限制，待排序的数据在一定范围内，所需额外空间也比较大
 * 基本思想就是，遍历一次原数组，用数据的值作为数组下标
 * 遇到相同的就加一，然后依次输出就行了
 * O(n)的复杂度，因为不是基于比较的排序
 * @author: lilin
 * @create: 2019-08-20 13:39
 **/
public class CountSort {
    public static void sort(int[] arr) {
        int max = Util.max(arr);
        int[] temp = new int[max + 1];
        Arrays.fill(temp, 0);
        for (int i = 0; i < arr.length; i++) {
            temp[arr[i]]++;
        }
        int index = 0;
        for (int j = 0; j < temp.length; j++) {
            while (temp[j] > 0) {
                arr[index] = j;
                temp[j]--;
                index++;
            }
        }
    }
}
```

```java
/**
 * @description: 堆排序
 * 堆排序是说，我们把n个数构造成一个最大堆，堆顶就是最大的元素，然后跟数组最后一个元素交换
 * 再把剩下的n-1个元素重新构造成一个最大堆，再跟数组的倒数第二个元素进行交换，这样直到数组的第一个元素
 * 我们把数组中的数据看成是一棵完全二叉树，完全二叉树的特性是说
 * 一棵二叉树，除了最后一层，全都是满的，而且最后一层的所有节点都是左对齐的
 * 然后我们利用最大堆/最小堆的特性，来对数组进行排序
 * 在完全二叉树里，有这个特性：
 * 左叶子节点的index = 父节点 * 2 + 1
 * 左叶子节点的index = 父节点 * 2 + 2
 * 这样就可以很方便的用数组下标表示堆中的各个节点了
 * 我们不断地对这棵树进行遍历，每次都选择出剩下最大的数，把它移到堆顶
 * 完成一次建堆操作，然后把堆顶的元素和数组最后的元素进行交换，最大的元素就被移到最后了
 * 堆排序的优势主要是，利用最大堆的特性，能够更快速的定位到最大的元素，而不必每次都全部遍历
 * 一个最直观的思路是把原数组的数据一个个读进来，构造一个最大堆
 * 但不需要这么做，叶子节点肯定是已经满足条件的
 * 只需要从非叶子节点开始，从右往左从下到上
 * 依次调整就行了
 * @author: lilin
 * @create: 2019-08-19 15:28
 **/
public class HeapSort {
    public static void adjustHeap(int[] arr, int start, int end) {
        int flag = arr[start]; // 非叶子节点元素
        for (int i = (2 * start + 1); i <= end; i *= 2) {
            // 找到子节点里较大的一个
            if (i < end && arr[i] < arr[i + 1]) {
                i++;
            }
            // 已经是最大堆了，就直接跳出循环
            // 为什么只判断了一层子节点，就不往下了？因为下面的已经先是最大堆了
            if (flag >= arr[i]) {
                break;
            }
            // 如果不是，子节点移上去
            // 不用担心移上去之后会破坏之前的大小顺序，因为移上去的数，肯定比叶子节点大
            arr[start] = arr[i];
            start = i;
        }
        arr[start] = flag;
    }

    public static void sort(int[] arr) {
        int n = arr.length;
        // 初始建堆
        // 从右往左，从下往上，第一个非叶子节点index是n / 2
        for (int i = n / 2; i >= 0; i--) {
            // 依次调整成堆，从这个index开始，到数组末尾
            adjustHeap(arr, i, n - 1);
        }

        for (int i = n - 1; i >= 0; i--) {
            Util.swap(arr, 0, i);
            adjustHeap(arr, 0, i - 1);
        }
    }
}
```

```java
/**
 * @description: 基数排序
 * 有10个桶，分别对应0-9
 * 先比较个位上的数字，放到对应的桶里面，再依次收集起来，这样个位有序
 * 再比较百位上的数字，放到对应的桶里面，再依次收集起来，这样百位有序
 * 直到最大位都比完了，最后一次收集起来，全部有序
 * @author: lilin
 * @create: 2019-08-20 14:25
 **/
public class RadixSort {
    public static void sort(int[] arr) {
        int maxBit = getMaxBit(arr);
        for (int i = 0; i < maxBit; i++) {
            List<List<Integer>> buckets = allocate(arr, i);
            collect(arr, buckets);
        }
    }

    // 根据第几位，分配到对应的桶里去
    private static List<List<Integer>> allocate(int[] arr, int bit) {
        List<List<Integer>> buckets = new ArrayList<>();
        // 0-9一共10个桶
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int i = 0; i < arr.length; i++) {
            int n = getNBit(arr[i], bit);
            buckets.get(n).add(arr[i]);
        }
        return buckets;
    }

    private static void collect(int[] arr, List<List<Integer>> buckets) {
        int k = 0;
        for (int i = 0; i < buckets.size(); i++) {
            List<Integer> list = buckets.get(i);
            for (int j = 0; j < list.size(); j++) {
                arr[k] = list.get(j);
                k++;
            }
        }
    }
    
    // 数组中最大的一个数，有多少位
    private static int getMaxBit(int[] arr) {
        int max = arr[0];
        for (int ele : arr) {
            max = Math.max(ele, max);
        }
        return (max + "").length();
    }

    // 得到第n位上的数
    // 123 分别就是1 2 3
    private static int getNBit(int num, int bit) {
        for (int i = 0; i < bit; i++) {
            num /= 10;
        }
        return num % 10;
    }
}
```
</xmp>
<script
      type="text/javascript"
      src="https://s4.cnzz.com/z_stat.php?id=1278167771&web_id=1278167771"
    ></script>
<script src="assets/strapdown.js"></script>
</html>